package toOffer;

/**
 * @author YuanAo
 * @date 2024/7/22 10:00
 * @description 在完全二叉树中添加节点
 */

import java.util.ArrayList;

/**
 * 完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。
 *
 * 设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：
 *
 * CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
 * CBTInserter.insert(int v) 向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
 * CBTInserter.get_root() 将返回树的根节点。
 * 示例 1：
 * <p>
 * 输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
 * 输出：[null,1,[1,2]]
 * 示例 2：
 * <p>
 * 输入：inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
 * 输出：[null,3,4,[1,2,3,4,5,6,7,8]]
 */
public class toOffer7_3_43 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        toOffer7_3_43 tree = new toOffer7_3_43(root);
        tree.insert(1);
        tree.get_root();

    }

    private static ArrayList<TreeNode> list;

    public toOffer7_3_43(TreeNode root) {
        list = new ArrayList<>();
        list.add(root);
        list.add(root.left);
        list.add(root.right);

    }

    public int insert(int v) {

        return 0;
    }

    public TreeNode get_root() {

        return null;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
